package LinkedGraph;

import Graph.*;

import java.util.ArrayList;
import java.util.Scanner;

public class LinkedGraph extends Graph implements IGraph {
    public GraphKind kind ;
    public  int vexNum,arcNum;
    public  VNode[] vexs;



    public LinkedGraph(ArrayList<Vertex> vertexList) {
        super();
        this.vertexList = vertexList;
    }

    public LinkedGraph(GraphKind kind, int arcNum, Vertex[] vexs, int[][] arcs) {
        super(kind, arcNum, vexs, arcs);
        vertexList = new ArrayList<>();
        createGraph(vexs, arcs);
    }

    /**
     * 通过二维数组创建图
     *
     * @param vexs
     * @param arcs
     */
    private void createGraph(Vertex[] vexs, int[][] arcs) {
        // 填充顶点表
        for (int i = 0; i < vexs.length; i++) {
            vertexList.add(vexs[i]);
        }
        // 填充边链表
        for (int i = 0; i < vexNum; i++) {
            Arc nextArc = vertexList.get(i).next;
            for (int j = 0; j < vexNum; j++) {
                // 存在邻接关系,则加入该顶点边链表
                if (arcs[i][j] != 0 && arcs[i][j] < INFINITY) {
                    Arc arc = new Arc(j, arcs[i][j], null);
                    if (nextArc == null) { // 添加顶点i的第一条边(弧)
                        vertexList.get(i).next = arc;
                    } else { // 添加顶点i的第2~j条边
                        nextArc.next = arc;
                    }
                    nextArc = arc;
                }
            }
        }
    }

    public void creatGraph() {
        Scanner sc=new Scanner(System.in);
        System.out.println("请输入图的类型：");
        GraphKind kind =GraphKind.valueOf(sc.next());
        switch(kind){
            case UDG:
                createUDG();;
                return ;
            case UDN:
                createUDN();
                return;
        }
    }
    private void createUDG() {
    }
    private void createUDN() {
        Scanner sc=new Scanner(System.in);
        System.out.println("请分别输入图的顶点数、图的边数：");
        vexNum=sc.nextInt();
        arcNum=sc.nextInt();
        vexs=new  VNode[vexNum];
        System.out.println("请输入图的各个顶点：");
        for(int k=0;k<arcNum;k++){
            int v=locateVex(sc.next());
            int u=locateVex(sc.next());
            int value =sc.nextInt();
            addArc(v,u,value);
            addArc(u,v,value);
        }
    }
    public void addArc(int v,int u,int value){
        ArcNode arc=new ArcNode(u,value);
        arc.nextArc=vexs[v].firstArc;
        vexs[v].firstArc=arc;
    }

    @Override
    public int getVexNum() {
        return vexNum;
    }

    @Override
    public int getArcNum() {
        return arcNum;
    }

    @Override
    public Object getVex(int v) {
        return vertexList.get(v);
    }

    @Override
    public int locateVex(Object vex) {
        for (int i = 0; i < vertexList.size(); i++) {
            if (vertexList.get(i).data.equals(((Vertex) vex).data)) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public int firstAdjVex(int v) throws Exception {
        if(v<0 && v>=vexNum)
            throw new Exception("第"+v+"个顶点不存在！");
        VNode vex=vexs[v];
        if(vex.firstArc!=null)
            return vex.firstArc.adjVex;
        else
            return  -1;
    }

    @Override
    public int nextAdjVex(int v, int w)throws Exception {
        if(v<0 && v>=vexNum)
            throw  new Exception("第"+v+"个顶点不存在！");
        VNode vex=vexs[v];
        ArcNode arcvw=null;
        for(ArcNode arc=vex.firstArc;arc!=null;arc=arc.nextArc)
            if(arc.adjVex ==w){
                arcvw=arc;
                break;
            }
        if(arcvw!=null && arcvw.nextArc!=null)
            return arcvw.nextArc.adjVex;
        else
            return -1;
    }

    protected void dfs(int v) {
        visited[v] = true;
        dfsList.add(getVex(v));

        Arc p = vertexList.get(v).next;
        // 查找顶点v的邻接表中未被方向的下一个顶点
        while (p != null) {
            if (!visited[p.index]) {

                dfs(p.index);
            }
            p = p.next;

        }
    }

    @Override
    public void showVexs() {

    }

    @Override
    public void showArcs() {
 
    }


    public void bfs(int v) {
        Arc p = vertexList.get(v).next;
        if (!visited[v]) {
            visited[v] = true;
            queue.offer(v);
        }
        // 遍历顶点v的边链表
        while (p != null) {
            if (!visited[p.index]) {
                visited[p.index] = true;
                queue.offer(p.index);
            }
            p = p.next;
        }
        // 从顶点v的各个未被访问的邻接点开始bfs
        if (!queue.isEmpty()) {
            bfsList.add(getVex(queue.poll().intValue()));
            if (!queue.isEmpty()) {
                bfs(queue.peek().intValue());
            }
        }
    }
}